#
# @lc app=leetcode.cn id=873 lang=python3
#
# [873] 最长的斐波那契子序列的长度
#

# @lc code=start
class Solution:
    def lenLongestFibSubseq(self, arr: List[int]) -> int:
        n, dic = len(arr), {a:i for i,a in enumerate(arr)}
        dp = [[0]*n for _ in range(n)]
        res = 0
        for j in range(1, n-1):
            for k in range(j+1, n):
                if arr[k]-arr[j] in dic and dic[arr[k]-arr[j]] < j:
                    dp[j][k] = max(3, dp[dic[arr[k]-arr[j]]][j] + 1)
                    res = max(res, dp[j][k])
        return res
# @lc code=end